package codingStudy.netEase2018Spring;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author zcxv
 * @category 跳石板问题
 */
public class JumpSlate {

	/**
	 * @param N
	 *            位置起点
	 * @param M
	 *            位置终点
	 * @return 最少需要几次可以从起点跳跃至终点
	 */
	static int slove(int N, int M) {
		// 1.初始化石板路
		int size = M - N + 1;
		Integer[] road = new Integer[size];
		for (int x = 1; x < size; x++) {
			road[x] = Integer.MAX_VALUE;
		}
		road[0] = 0;
		// 2.根据状态转移方程，动态规划石板
		for (int i = 0; i < size; i++) {
			if (road[i] == Integer.MAX_VALUE) {
				road[i] = 0;
				continue;
			}
			ArrayList<Integer> factorList = getFactor(i + N);
			if (factorList == null) {
				continue;
			}
			for (Integer t : factorList) {
				if (i + t < size)
					road[i + t] = Math.min(road[i + t], road[i] + 1);
			}

		}
		// 3.得出结果

		return road[size - 1];

	}

	/**
	 * 求解全部约数
	 * 
	 * @param num
	 * @return
	 */
	static ArrayList<Integer> getFactor(int num) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 2; i <= Math.sqrt(num); i++) {
			if (num % i == 0) {
				list.add(i);
				if (num / i != i) {
					list.add(num / i);
				}
			}

		}
		return list;

	}

	public static void main(String[] args) {
		/*
		 * Scanner scanner = new Scanner(System.in); int n = scanner.nextInt();
		 * int m = scanner.nextInt();
		 */
		System.out.println(slove(4, 24));
	}
}